%\section{Formulation}

\section{Proposed Algorithm}
\label{formulation}
% with unit action cost. 

In this paper, we tackle classical planning problems
that can be formulated using STRIPS or ADL. 
Given a classical planning task $\mathcal{T}$ 
with an initial state $s_{0}$,  $\mathcal{A}_{h}$ 
is a best-first search algorithm guided
by heuristic function $h$. $\mathcal{S}$ 
is  the set of states explored by $\mathcal{A}_{h}$.

\begin{defn}[Order of states]
Given a best-first search procedure $\mathcal{A}_{h}$ on $\mathcal{S}$ guided
by $h$,  the relation $\mathcal{R} \subseteq \mathcal{S} \times \mathcal{S}$ 
is defined as follows:  for any states $a$ and $b$, $\mathcal{R}(a, b)$ holds if and only if $a$ is 
explored before $b$ according to $\mathcal{A}_{h}$. We use $a < b$ to denote $\mathcal{R}(a, b)$.  
\end{defn}
 
It is easy to see that states in $\mathcal{S}$
can be sorted according to $\mathcal{R}$ to a total order. 
Let $\mathcal{L}$ be an ordered list of all states in $\mathcal{S}$  
where the initial state $s_{0}$ is the first state
and the first goal state found by $\mathcal{A}_{h}$
is the last state in $\mathcal{L}$, we can define a plateau as follows. 

\begin{defn}[Plateau and Exit]
Given a heuristic function $h$, let $P$ be a sub-sequence of $\mathcal{L}$, $P$ is 
a {\bf plateau} if $|P| > 1$,  and for every state $s \in P$,  $h(s) \ge l $. 
A state $e_{P}$ is an {\bf exit} of $P$ if $h(e_{P}) < l $ and $e_{P}$ is an immediate 
successor of some state in $P$.  
\end{defn}

% Define dead end here ..
% A state in $\mathcal{S}$ is called a dead end if and only if 
% goal is not reachably. We also assume that heuristic function can identify it 
% and define the heuristic value as $\infty$ (well, that heuristic function might not able to identify it)
% we assume that our heuristic function's judgement of the 
%reachability is correct, meaning that 
% if heuristic function deems state $s$ a dead-end, it is indeed a dead-end. 

%%%%%% decide if we want to insert here. 
% Note that our definition of plateau here is different than that defined in 
% [When Gravity]. We allow nodes that is higher than the plateau 
% to reside inside the plateau. Part of this is because that a typical 
% best first search will indeed explore these states in a sequence. 
% Also the exit of the plateau is different.   There are multiple possible 
% exits for there plateau in a SAT problem. 
% In our planning case, there is one exit for a plateau, but they does 
% not need to be fully connected. except that
% there are both reachable from some initial state. 
% Also, we assume that search is always on a bench while the plateau 

% the state in $L$ that is right before $P$ is called the entrance of $P$, 
% and the state immediately after the last state of $P$ in $L$ is called 
% the exit of $P$. A plateau is called a maximum plateau if and only if 
% the heuristic value of its existing state $h(e_{P})$ is less than $l$, the level of $P$. 



\nop{
To characterize the performance of a heuristic-guided best-first search, 
we use the effective branch factor as a metric. 
\begin{defn}[Effective Branch Factor]
Given a best-first search algorithm $\mathcal{A}_{h}$ for a planning task $T$ 
with state space $\mathcal{S}$, if $d$ is the length of the goal path found by  $\mathcal{A}_{h}$, 
the effective branch factor of $h$, denoted by 
$b_{h}$, equals to $\log_{d-1} |\mathcal{S}| $.  
\end{defn}

The effective branch factor grasps the 
average branch factor of $A_{h}$. It is easy to see 
that perfect heuristic function gives $b_{h} =1 $ 
and a blind heuristic $h(s) = 0$ has an effective 
branch factor equals to the branch factor of $T$.
In the consequent sections, we use the effective branch 
factor $b_{h}$ to estimate the number of states
explored by $\mathcal{A}_{h}$. 
}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% TODO: More definitions
